/*
 * @lc app=leetcode.cn id=102 lang=javascript
 *
 * [102] 二叉树的层序遍历
 */

// 方法1 设计 一个 二叉树的结构
function TreeNode(left, val, right) {
  this.val = val === undefined ? 0 : val
  this.left = left === undefined ? null : left
  this.right = right === undefined ? null : right
}
// 入参
// [
//     [9],
//     3,
//     [
//         [15],
//         20,
//         [17]
//     ]
// ]

function make(array) {
  if (array.length === 0) return []
  else if (array.length === 1 && Object(array[0]) !== array[0])
    return new TreeNode(null, array[0], null)
  else if (array.length === 1) return make(array[0])
  return new TreeNode(make(array[0]), array[1], make(array[2]))
}

// let tree = make([[[9], 3, [[15], 20, [17]]]])
let tree = make([[]])
console.log(tree)
// 得到tree之后，可以进行遍历
// 前 中 后 序遍历
// 层序遍历
// 1-2 dfs
function levelOrder(root) {
  let result = []
  function dfs(node, level) {
    if (result.length < level + 1) {
      result.push([])
    }
    result[level].push(node.val)
    dfs(node.left, level + 1)
    dfs(node.right, level + 1)
  }
  dfs(root, 0)
  return result
}

// 1-1 bfs

// function levelOrder(root) {
//   let queue = []
//   queue.push([root])
//   let result = []
//   while (queue.length) {
//     let nodes = queue.shift()
//     let temp = []
//     let currentLevel = []
//     for (let node of nodes) {
//       temp.push(node.val)
//       node.left && currentLevel.push(node.left)
//       node.right && currentLevel.push(node.right)
//     }
//     if (currentLevel.length) {
//       queue.push(currentLevel)
//     }
//     if (temp.length) result.push(temp)
//   }

//   return result
// }
// function levelOrder(root) {
//   let queue = [].push(root)
//   let result = []
//   // let set = new Set()
//   // visited = set.add(root)
//   while (queue.length) {
//     let currentLevel = []
//     let levelSize = queue.length
//     while (levelSize) {
//       let node = queue.shift()
//       currentLevel.push(node.val)
//       if (node.left) queue.push(node.left)
//       if (node.right) queue.push(node.right)
//       levelSize--
//     }
//     result.push(currentLevel)
//   }
//   return result
// }

// let r = levelOrder(tree)
// console.log(r)

// 方法2
// 我用 bfs 的方式实现了效果，问题出在了 数据结构上
// 这里的不完全二叉树，我用的打平的 数组 和 父 left right 节点的 index 关系来维护了一份二叉树

// ;[3, 9, 20, null, null, 15, 7]

// [
//     [3],
//     [9, 20],
//     [15, 7]
// ]
// var levelOrder = function (root) {
//   if (root.length === 0) return []
//   if (root.length === 1) return [root]
//   let queue = []
//   queue.push([root[0]])
//   let result = []
//   while (queue.length) {
//     let nodes = queue.shift()
//     result.push(nodes)

//     let tempArr = []
//     for (let node of nodes) {
//       let index = 0
//       inner: for (let i = 0; i < root.length; i++) {
//         if (root[i] === node) {
//           index = i
//           break inner
//         }
//       }
//       root[index * 2 + 1] && tempArr.push(root[index * 2 + 1])
//       root[index * 2 + 2] && tempArr.push(root[index * 2 + 2])
//     }
//     if (tempArr.length) {
//       queue.push(tempArr)
//     }
//   }
//   return result
// }
// // @lc code=end
// let r = levelOrder([3, 9, 20, null, null, 15, 7])
// console.log(r)
